package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/evaluate-boolean-binary-tree/'>计算布尔二叉树的值(Evaluate Boolean Binary Tree)</a>
 * <p>
 * 给你一棵 完整二叉树 的根，这棵树有以下特征：
 *     <ul>
 *         <li>叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。</li>
 *         <li>非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。</li>
 *     </ul>
 *     计算 一个节点的值方式如下：
 *     <ul>
 *         <li>如果节点是个叶子节点，那么节点的 值 为它本身，即 True 或者 False 。</li>
 *         <li>否则，计算 两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算 。</li>
 *     </ul>
 *     返回根节点 root 的布尔运算值。
 * </p>
 * <p>完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。</p>
 * <p>叶子节点 是没有孩子的节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [2,1,3,null,null,0,1]
 *                  OR                     OR
 *                 /  \                   /  \
 *              True   AND      ==>    True False  ==> True
 *                     / \
 *                 False True
 *      输出：true
 *      解释：上图展示了计算过程。
 *              AND 与运算节点的值为 False AND True = False 。
 *              OR 运算节点的值为 True OR False = True 。
 *              根节点的值为 True ，所以我们返回 true 。
 *
 * 示例 2：
 *      输入：root = [0]
 *      输出：false
 *      解释：根节点是叶子节点，且值为 false，所以我们返回 false 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在 [1, 1000] 之间。</li>
 *     <li>0 <= Node.val <= 3</li>
 *     <li>每个节点的孩子数为 0 或 2 。</li>
 *     <li>叶子节点的值为 0 或 1 。</li>
 *     <li>非叶子节点的值为 2 或 3 。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/20 16:39
 */
public class LC2331EvaluateBooleanBinaryTree_S {
    static class Solution {
        public boolean evaluateTree(TreeNode root) {
            if (root.left == null && root.right == null) {
                // 0：返回 false；1：返回 true。
                return root.val == 1;
            }
            if (root.left != null && root.right != null) {
                // OR
                if (root.val == 2) {
                    return evaluateTree(root.left) || evaluateTree(root.right);
                }
                // AND
                if (root.val == 3) {
                    return evaluateTree(root.left) && evaluateTree(root.right);
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(3);
        root1.right.left = new TreeNode(0);
        root1.right.right = new TreeNode(1);

        TreeNode root2 = new TreeNode(0);

        Solution solution = new Solution();
        System.out.println(solution.evaluateTree(root1));
        System.out.println(solution.evaluateTree(root2));
    }
}
